/*
 * @lc app=leetcode.cn id=106 lang=cpp
 *
 * [106] 从中序与后序遍历序列构造二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution
{
public:
    TreeNode *traval(vector<int> &inorder, int inorderbegin, int inorderend, vector<int> &postorder, int postorderbegin, int postorderend)
    {
        //参数是中序和后序数组以及开始结束位置
        //区间都是左闭右开
        //首先根据后序遍历判断分界点
        //首先判断后序数组是否为空 为空直接返回
        if (postorderbegin == postorderend)
        {
            return NULL;
        }
        TreeNode *root = new TreeNode(postorder[postorderend - 1]);
        if (postorderend - postorderbegin == 1)
        {
            return root; //如果是叶节点是直接返回
        }

        //开始确定中序遍历的起始和终止位置
        //先找到切割点
        int mysplit = -1;
        for (int i = 0; i < inorder.size(); i++)
        {
            if (inorder[i] == root->val)
            {
                mysplit = i;
                break;
            }
        }

        int leftinorderbegin = inorderbegin;
        int leftinorderend = mysplit;

        int rightinorderbegin = mysplit + 1;
        int rightinorderend = inorderend;

        //确定后序遍历起始和终止位置
        //因为中序和后序遍历的长度肯定一样
        int leftpostorderbegin = postorderbegin;
        int leftpostorderend = postorderbegin + leftinorderend - leftinorderbegin;

        int rightpostorderbegin = leftpostorderend;
        int rightpostorderend = postorderend - 1;

        root->left = traval(inorder, leftinorderbegin, leftinorderend, postorder, leftpostorderbegin, leftpostorderend);
        root->right = traval(inorder, rightinorderbegin, rightinorderend, postorder, rightpostorderbegin, rightpostorderend);
        return root;
    }
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder)
    {
        if (inorder.size() == 0)
        {
            return NULL;
        }
        //区间始终是左闭右开！
        return traval(inorder, 0, inorder.size(), postorder, 0, postorder.size());
    }
};
// @lc code=end
